Reinforcement Learning

Table of Contents

1. Markov Decision Process

1.1. Definition

1.1.1. Chain

  • It is discrete stochastic process in which an agent take actions \(A_t\) based on the current state \(S_t\), to get to the new state \(S_{t+1}\) and get reward \(R_{t+1}\).
  • The space of states is denoted as \(\mathcal{S}\), the spaces of actions at a state \(s\) as \(\mathcal{A}(s)\), and the space of rewards as \(\mathcal{R} \subset \mathbb{R}\).
    • \(\mathcal{S}^+\) is used when it contains terminal states.
  • Tabular
    • The process is tabular if all states and actions can be listed.

1.1.2. Dynamics

  • The dynamics of the agent-environment interaction is given by the probability distribution: \[ p(s', r |s, a) := \mathrm{P}[S_{t+1}=s', R_{t+1}=r\mid S_t = s, A_t = a]. \]
  • Complete Knowledge
    • If the dynamics is known one is said to be having the complete knowlege.
  • Markov Property
    • The probability only depend on the current state and action.

1.1.3. Policy

  • Policy is the probability of action (or function to action) at each state that needs to be optimized: \[ \pi(a|s) \text{\quad or\quad } \pi(s) = a. \]

1.1.4. Return

  • Return is the weighted sum of the future rewards: \[ G_t := \sum_{k=t+1}^\infty \gamma^{k-t-1}R_k \]
  • where \(\gamma\) is often a value between 0 and 1.
  • In the episodic case the process terminates, marking the end of an episode, also the summation, in contrast to the continuing case.

1.1.5. Trajectory

  • Sequence, possibly infinite, of states, actions, rewards produced by the process.
  • It can be expressed as random variables, \[ S_0, A_0, R_1, S_1, A_1, R_2,\dots, R_T,S_T \]
  • or as values, \[ s_0^m, a_0^m, r_1^m, s_1^m, a_1^m,\dots, r_T^m, s_T^m. \]

1.1.6. State Value Function

  • Expected return at state \(s\), that varies depending on the policy \(\pi\).
  • \[ v_\pi(s) := \mathrm{E}_\pi[G_t\mid S_t = s]. \]
  • It is typically impossible to find it directly.
  • Terminal states has value of zero by definition.

1.1.7. Action Value Function

  • Expected return of a state-action pair \((s, a)\). It also depends on \(\pi\).
  • \[ q_\pi(s,a) := \mathrm{E}_\pi[G_t\mid S_t = s, A_t = a] \]

1.2. Bellman Equations

For any policy \(\pi\),

\begin{align*} v_\pi(s) &= \sum_{a\in \mathcal{A}(s)}\pi(a|s)q_\pi(s,a)\\ q_\pi(s,a) &= \sum_{s'\in\mathcal{S}, r\in\mathcal{R}}p(s',r|s,a)[r+\gamma v_\pi(s')]\\ \end{align*}

This is due to the fact \[ \mathrm{E}_\pi[G_{t+1}\mid s, a] = \mathrm{E}_\pi[v_\pi(S_{t+1})\mid s,a] \] by the law of total probability

Consequently,

\begin{align*} v_\pi(s) &= \sum_{a\in \mathcal{A}(s)}\pi(a | s)\sum_{s'\in \mathcal{S}, r\in \mathcal{R}} p(s', r |s, a)(r+\gamma v_\pi(s'))\\ q_\pi(s,a) &= \sum_{s'\in\mathcal{S}, r\in\mathcal{R}}p(s',r|s,a)\left[r+\gamma \sum_{a'\in \mathcal{A}(s')}\pi(a'|s')q_\pi(s',a')\right] \end{align*}

1.3. Optimization

The goal is to find the optimal policy \(\pi_*\) which satisfies:

  • \[ \forall \pi, \forall s \in \mathcal{S}, v_*(s) := v_{\pi_*}(s) \ge v_\pi(s), \]
  • \[ \forall \pi, \forall s\in \mathcal{S}, \forall a \in \mathcal{A}(s), q_*(s,a) := q_{\pi_*}(s,a) \ge q_\pi(s,a). \]

The existence of such policy is guaranteed.

1.3.1. Bellman Optimality

\[ v_*(s) = \max_{a\in\mathcal{A}(s)} q_*(s, a). \]

This must be the case, since otherwise it is not optimal. There could be multiple actions values that are equal, in that case there's multiple optimal policy.

2. Generalized Policy Iteration

  • GPI

Every reinforcement learning can be seen as a generalized policy iteration

\[ \pi_0 \xrightarrow{E} v_{\pi_0} \xrightarrow{I} \pi_1 \xrightarrow{E} \dots \xrightarrow{I} \pi_* \xrightarrow{E} v_* \]

2.1. Policy Evaluation

2.1.1. Model-Based

The approximate value of the state value function and action value function can be calculated by repeatedly calculating the value at each point \(V(s)\), \(Q(s,a)\) according to the Bellman equations.

It is guaranteed to converge.

2.1.2. Value Iteration

The value does not needs to reach convergence.

2.2. Model-Free

Since the model is unknown, estimating the action value is more feasible.

2.2.1. Monte Carlo Evaluation

Estimate the state value function of the action-value pair state \(s := (\tilde{s}, \tilde{a})\) within the Markov reward process. \(V(s) = Q(\tilde{s},\tilde{a})\).

Given \(M\) trajectory samples of an MRP, it can be approximated by the average: \[ \mathrm{E}_\pi[G_t\mid S_t = s] \approx V(s) = Q(\tilde{s},\tilde{a}) := \frac{1}{C(s)}\sum_{m=1}^M\sum_{\tau = 0}^{T_m-1}\mathbf{1}[s_\tau^m = s]g_\tau^m \] where \(C(s)\) is the counting function of the occurence of \(s\)

It can be divided into updates after each trajectory following the update rule: \[ Q(\tilde{s}_t^m, \tilde{a}_t^m) = V(s_t^m) \leftarrow V(s_t^m) + \frac{1}{C(s_t^m)}(g_t^m - V(s_t^m)) \] Here \(C(s_t^m)\) only counts up to the \(m\)th trajectory, up to time \(t\) within the last trajectory.

\(g_t^m\) for each \(s_t^m\) are determined after the \(m\)th trajectory terminates. Then, the states within that trajectory would be updated. It correctly calculates the average at each iteration. \[ \frac{(V(s_t^m)-1)V(s_t^m) + g_t^m}{C(s_t^m)} \]

Target is what the estimates are moved towards at each update.

2.2.2. Constant-α Monte Carlo

The update rule is modified to be \[ V(s_t^m) \leftarrow V(s_t^m) + \alpha (g_t^m - V(s_t^m)) \] where the stepsize \(\alpha\in (0,1]\) is a constant.

If \(\alpha\) is small, it converges slowly, if \(\alpha\) is large, the estimate is noisy. The best hyperparameter \(\alpha\) is problem dependent.

2.2.3. Off-Policy Method

In on-policy method, the behavior policy \(b\) is equal to the target policy \(\pi\): \(b(a|s) = \pi(a|s)\). But in off-policy method \(b\neq\pi\), so the importance sampling is required: \[ q_\pi(s,a) = \mathrm{E}_\pi[G_t\mid S_t = s, A_t = a] = \mathrm{E}_b\left[\rho G_t\mid S_t = s, A_t = a\right] \] where \(\rho\) is the product of the ratio of probability over the remainder of the trajectory: \[ \rho := \frac{p_\pi(G_t)}{p_b(G_t)} = \prod_{\tau = t+1}^{T-1}\frac{\pi(A_\tau \mid S_\tau)}{b(A_\tau\mid S_\tau)}. \]

  • \(\rho_t^m\) is multiplied to the plain \(g_{t,b}^m\) to obtain \(g_t^m\) at each update phase.
  • Coverage is required \[ \pi(a|s) > 0 \implies b(a|s) > 0 \]
    • Behavior policy must be able to take all the actions that target policy takes.
    • This ensures that there's always data in the limiting case.
  • It explores more, has high variance.

2.2.4. n-Step Temporal Difference Learning

  • n-Step TD

If an episode takes significant amount of time, or even infinite time, the process of learning is slow. So one needs to learn during an episode.

2.2.4.1. Target

The target \(g_t^m\) is modified to: \[ g_{t;t+n}^m = \sum_{\tau = t+1}^{t+n < T}\left(\gamma^{\tau-t-1}r_\tau^m\right) + \gamma^n V(s_{t+n}^m). \] If \(t+n \ge T\), it is \(g_{t;t+n}^m = g_t^m\).

This allows one to computer the return only with the knowledge through \(n\)-step forward into the future. Using a value estimate in the target is called bootstrapping

2.2.4.2. Hyperparameter
  • \(n\) is a hyperparameter
    • when \(n=\infty\) TD is identical to MC.
    • \(\alpha\) can be larger compared to MC, when \(n\) is small. It converges faster without much noise.
    • This is because the variance is reduced by bootstrapping, therefore larger steps can be taken.
    • For small \(n\), typically slightly higher \(\alpha\) performs better.
    • For larger \(n\), one learn more from a single episode. Since the signal from farther away can be considered, when \(n\) is large.
      • So the exploration of state space is fast, yet noisier.
2.2.4.3. Properties
  • Batch training is performing the training on a fixed batch, unlike the real time data.
  • MC and TD arrive at different estimates under batch training, MC finds the one that minimize mean-squared error, which is achieved by average, and TD finds the one with the maximum-likelihood of the MRP \(\hat{p}(s', r|s)\).
    • \(\hat{p}(s',r|s) = C(s',r|s)/C(s)\) to estimate \(v\) is equivalent to 1-step batch TD.

TD's criteria is better for predicting returns.

  • Because it more directly uses the assumption of the MRP.

2.3. Policy Improvement

The optimal deterministic policy \(\pi_*\): \[ \pi_*(s) = \operatorname*{argmax}_a q_*(s,a), \] Therefore, the approximation of the optimal policy is chosen greedily: \[ \pi'(s) = \operatorname*{argmax}_a q_\pi(s,a). \]

2.3.1. Policy Improvement Theorem

\[ \forall s\in \mathcal{S}, v_\pi(s) \le v_{\pi'}(s) \] If \(\pi\) is greedy with respect to \(v_{\pi'}\), then \(\pi = \pi_*\).

2.3.2. Monte Carlo Control

By the constant-α Monte Carlo the Q-table is obtained. The policy can be improved greedily with respect to the Q-table: \[ \pi'(s) = \operatorname*{argmax}_aQ(s,a). \]

2.3.2.1. Exploration-Exploitation Tradeoff
  • To discover optimal policies, all state-action pairs must be explored, but to get high returns, one must exploit known high value pairs.
  • If the policy does not explore the unexplored state, the policy might never be able to discover the state with high state value.
  • Therefore, the policy needs to be soft: \[ \forall s\in \mathcal{S}, \forall a\in \mathcal{A}(s), \pi(a|s) > 0. \]
    • with infinite data, \(\pi_*\) is always discoverable, if the policies are chosen to be soft.
2.3.2.2. ε-Greedy Policy
  • With probability \(\epsilon\), take an action selected uniformly form \(\mathcal{A}(s)\) otherwise select the maximum Q.

3. Temporal Difference Control

  • As long as each process does their job partially, the algorithm will converge toward the optimum.

3.1. n-Step Sarsa

  • On Policy TD Control
  • The temporal difference learning is used. And the updates are applied during the epoisodes.
  • "Sarsa" comes from 1-step Sarsa, in which every update operates on \(s_t^m, a_t^m, r_{t+1}^m, s_{t+1}^m, a_{t+1}^m\).

3.2. Q-Learning

  • n-Step Q-Learning

3.2.1. Target

  • The target is adjusted to:
    • \[ g_{t;t+n}^m = \sum_{\tau = t+1}^{t+n < T}\left(\gamma^{\tau-t-1}r_\tau^m\right) + \gamma^n \max_aQ(s_{t+n}^m, a). \]
      • If \(t+n \ge T\), it is \(g_{t;t+n}^m = g_t^m\).
    • Assume the best case scenario at the last state.
  • The max operator means this is off-policy, since the return is not according to the policy.
  • Under the behavior policy, \(Q\) is targeting \(q_*\). It is following the policy \(\pi_\text{greedy}\) defined to choose the maximum action value.
    • In contrast to the on-policy methods, in which we are approximating the optimal policy with the previous best behavior policy.
  • The updates happen before the actions are taken, unlike TD in which updates happen after the actions are taken.

3.2.2. Properties

  • With the maximum operator the creeping in of nearby low values is prevented, as presented in the example of cliff walking.

3.3. Expected Sarsa

3.3.1. Target

  • The target is adjusted to:
    • \[ g_{t;t+n}^m = \sum_{\tau = t+1}^{t+n < T}\left(\gamma^{\tau-t-1}r_\tau^m\right) + \gamma^n \sum_a \pi(a|s_{t+1}^m)Q(s_{t+n}^m, a). \]
      • If \(t+n \ge T\), it is \(g_{t;t+n}^m = g_t^m\).
  • Expected return at the last state.
  • It is less noisy, but the computation is more expensive.
  • This is on-policy method, if \(b = \pi\).
  • Expected sarsa is more efficient version of sarsa. Sarsa estimates \(Q\) only with sampling, expected sarsa does it also with expected value.

4. Function Approximation

4.1. Generalization

If an agent only visits a minuscule subset of all states, how should it generalize that experience to select high reward actions over the remaining states?

  • Supervised Learning
    • Learn from noisy samples.
    • SL applied for RL is called function approximation.

4.2. On Policy Evaluation

  • When \(\mathcal{S}\) is large, the degree of freedom is reduced by assuming: \[ v_\pi(s) \approx \hat{v}(s, \mathbf{w}) \]
  • where \(\mathbf{w}\in \mathbb{R}^d\).
    • Since a state \(s\) is arbitrary there must exists features \(x_i : \mathcal{S}\to \mathbb{R}^n\) that describes the state.

4.2.1. Value Error

  • \[ \overline{\mathrm{VE}}_\pi(\mathbf{w}) = \sum_{s\in\mathcal{S}}\mu_\pi(s)\left[v_\pi(s) - \hat{v}(s,\mathbf{w})\right]^2 \] where \(\mu_\pi\) is a distribution over states according to the policy \(\pi\).

4.2.2. Stochastic Gradient Descent

  • The goad is to find \(\hat{v}\) that approximately optimize the value error.
4.2.2.1. Assume
  • On policy: States are visited in proportion to \(\mu_\pi\).
  • \(\hat{v}\) is differentiable with respect to \(\mathbf{w}\)
  • The observation \(U_t\) is a surrogate for the target \(v_\pi(S_t)\)
4.2.2.2. Update Rule
  • \[ \mathbf{w} \leftarrow \mathbf{w} + \alpha[U_t - \hat{v}(S_t, \mathbf{w})]\nabla\big|^\mathbf{w} \hat{v}(S_t, \mathbf{w}) \]
  • If the target \(U_t\) is unbiased, then \(\mathbf{w}\) will converge to a local optimum of value error.

4.2.3. Gradient Monte Carlo

  • MC with modified update rule.
4.2.3.1. Target
  • \(U_t = G_t\)
4.2.3.2. Properties
  • It may be significantly slow, since it requires an episode to end before it updates.
  • If the value estimator function is a linear value function of the form \[ \hat{v}(s,\mathbf{w}) = \mathbf{w}^\top\mathbf{x}(s) \] where \(\mathbf{x}(s)\) is a feature vector, the local minimum \(\mathbf{w}\) is the global mimimum \(\mathbf{w}\).
    • Since the linearity makes the optimization convex.

4.2.4. Semi-Gradient Temporal Difference

  • Semi-Gradient TD
4.2.4.1. Target
  • \[ U_t = R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}) \]
  • It's biased. Since \[ \mathrm{E}[\hat{v}(S_{t+1}, \mathbf{w})|S_t = s] \neq \mathrm{E}[v_\pi(S_{t+1}) | S_t = s] \implies \mathrm{E}[U_t| S_t=s] \neq v_\pi(s) \]
4.2.4.2. Properties
  • Update rule is not a true gradient step, because \(U_t\) depends on \(\hat{v}\) which depends on varying \(\mathbf{w}\).
    • \[ \nabla (\overline{\mathrm{VE}}_\pi(\mathbf{w}, U_t)) \neq (\nabla \overline{\mathrm{VE}}_\pi)(\mathbf{w}, U_t) \] therefore following the gradient does not maximally minimizes the value error.
    • And \(\mathrm{E}[\hat{v}(S_t, \mathbf{w})] \neq \mathrm{E}[v_\pi(S_t)]\) either, even for the VE optimum \(\hat{v}\).
    • That means we don't get graranteed convergence
  • In 1-step case, for the linear value function, \(\mathbf{w}\) will converge to a TD fixed point \(\mathbf{w}_\text{TD}\).
    • The closeness to the VE optimum is related to the attenuation factor \(\gamma\). For high \(\gamma\) near 1, the solution can be far apart from the true optimum.

4.3. On Policy Control with Function Approximation

  • Assumption
    • Action space \(\mathcal{s}\) is not large.
    • Episodic case. otherwise it is different
  • The state value function \(\hat{v}(s, \mathbf{w})\) is now action value function \(\hat{q}(s,a,\mathbf{w})\).

4.3.1. Semi-Gradient 1-Step Sarsa

4.3.1.1. Target
  • \[ U_t = R_{t+1} + \gamma \hat{q}(S_{t+1}, A_{t+1}, \mathbf{w}) \]
  • Normalized radial basis used as the features for a state.

4.4. Off Policy Methods with Function Approximation

4.4.1. The Deadly Triade

  1. Function Approximation
  2. Off-Policy Training
  3. Bootstrapping
  4. \(\leadsto\) stability and divergence issues.
  5. It is inevitable.

5. Policy Gradient Methods

5.1. Reinforce Algorithm

  • Monte Carlo algorithm
    • Update happens after a full episode is performed.
  • Assume
    • Policy \(\pi(a|s, \bm{\theta})\) is differentiable
  • Initial setup
    • Functional form of \(\pi\)
    • Initial \(\bm{\theta}\)
    • Step size \(\alpha\)
  • is often used to unconstrain the parameter \(\theta_i\).
    • And the policy at one point is the average of the parameters weighted by the normalized radial basis, and then applying softmax to it.
    • It is not exactly linear but good enough.
  • Update Rule
    • \[ \bm{\theta} \leftarrow \bm{\theta} + \alpha g_t^m \nabla\ln\pi(a_t^m|s_t^m, \bm{\theta}) \]
    • This reinforces the probability of taking action \(a_t^m\) when in state \(s_t^m\) in proportion to the return \(g_t^m\).
    • \(\ln\) is there to compensate for the effect of selection frequency on descent.
      • The high selection rate is exactly canceled by dividing the step by the propability.

5.2. Reinforce with Baseline

  • If \(\forall g_t^m \gg 1\), the optimization will take quite long. because the reinforce algorithm will never learn to not do things, only do more good things.
    • Replace \(g_t^m\) with \(g_t^m - b(s_t^m)\), where \(b\) is called the baseline.
    • Baseline can be any function that does not depend on action and does not make the problem diverge.
    • Natural choice of the baseline is the state value, the expected return of that state:
      • \[ b(s_t^m) = \hat{v}(s_t^m, \mathbf{w}) \]
      • The agent would prefer the action that increases the expected return.

5.2.1. Update Rule

\begin{align*} \delta &\leftarrow g_t^m - \hat{v}(s_t^m, \mathbf{w})\\ \mathbf{w} &\leftarrow \mathbf{w} + \alpha^{\mathbf{w}}\delta \nabla\big|^\mathbf{w} \hat{v}(s_t^m, \mathbf{w})\\ \bm{\theta} &\leftarrow \bm{\theta} + \alpha^{\bm{\theta}}\gamma^t\delta \nabla\big|^{\bm{\theta}}\ln\pi(a_t^m|s_t^m, \bm{\theta})\\ \end{align*}
  • It is exactly the combination of ((66865702-a5f4-4c57-a58b-0a182067473b)) and Reinforce algorithm.

5.3. Policy Gradient Theorem

  • The objective to optimize in the policy gradient method is
    • Episodic case: \[ v_{\pi_{\bm{\theta}}}(s_0) = \mathrm{E}_{\pi_{\bm{\theta}}}[G_0|S_0 = s_0] \]
  • Theorem
    • \[ \nabla\big|^{\bm{\theta}} v_{\pi_{\bm{\theta}}}(s_0) \propto \sum_{s\in \mathcal{S}}\mu_{\pi_{\bm{\theta}}}(s)\sum_{a\in \mathcal{A}(s)}q_{\pi_{\bm{\theta}}}(s, a)\nabla\big|^{\bm{\theta}}\pi(a|s, \bm{\theta}) \]
      • The gradient of the state value of the initial state, i.e. the gradient of the total return is proportional to the action value weighted average of the gradient of policy at each state-action pair.

If an algorithm approximates this direction \(\nabla\big|^{\bm{\theta}}v_{\pi_{\bm{\theta}}}\), it'll approximately optimize the objective.

5.4. Properties

  • PGM may be slow at converging because it takes smooth transition for it to converge, but because of that it is more likely to converge eventually without getting stuck.
  • It solves only for the policy.
    • No detailed knowledge is gained.
    • It bypasses the complexity.
  • It can learn stochastic policies.
    • The level of stochasticity can be learned!
    • On the other hand, \(\epsilon\)-greedy method only has a fixed stochasticity.
  • It avoids computationally intensive argmax operations.

5.5. Examples

  • Proximal Policy Optimization

6. References

Author: Jeemin Kim

Created: 2026-09-29 Tue 00:20